package com.bupt.algorithm;

import com.bupt.Algorithm.DFSAlgorithm;
import com.bupt.Algorithm.TraverseAlgorithm;
import com.bupt.Factory.ProjectFactory;
import com.bupt.basic.IBasicNetWork;
import com.bupt.basic.Project;
import com.bupt.entity.*;
import com.bupt.exception.BaseException;
import com.bupt.model.Limit;
import com.bupt.utils.StrategyString;

import java.util.*;

public class TrafficSystemLimitRouteFinder implements TrafficRouteAlgorithm {



    public TrafficSystemLimitRouteFinder() {
    }

    private String strategy=StrategyString.LENGTH;//默认算法是复杂均衡

    public void setStrategy(String strategy) {
        this.strategy = strategy;
    }



    //计算没有必经节点时的最短路径
    @Override
    public List<IBasicNetWork.BasicLink> findNoMust(Project project,List<IBasicNetWork.BasicLink> basicLinks, List<IBasicNetWork.BasicNode> commonNodes, IBasicNetWork.BasicNode sourceNode, IBasicNetWork.BasicNode targetNode) throws BaseException {
        //校验参数
        if(basicLinks==null||commonNodes==null||sourceNode==null||targetNode==null){
            return null;
        }

        //校验 起点和重点是否在集合中
        if(!commonNodes.contains(sourceNode)||!commonNodes.contains(targetNode)){
            return null;
        }

            HashMap<IBasicNetWork.BasicNode,Integer> nodeIntegerMap = new HashMap<>();
            long[][] matrix=new long[commonNodes.size()][commonNodes.size()];
            int ori=0;
            int dest=0;
            for (int i = 0; i < commonNodes.size(); i++) {
                if(commonNodes.get(i).equals(sourceNode)){
                    ori=i;
                }
                if(commonNodes.get(i).equals(targetNode)){
                    dest=i;
                }
                nodeIntegerMap.put(commonNodes.get(i),i);
            }

            //初始化矩阵
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix.length; j++) {
                    if(i==j){
                        matrix[i][j]=0;
                    }else {
                        matrix[i][j]=-1;
                    }
                }
            }

            for (IBasicNetWork.BasicLink basicLink : basicLinks) {
                IBasicNetWork.BasicNode fromNode = project.searchNodeById(basicLink.getNodeHead());
                IBasicNetWork.BasicNode  toNode = project.searchNodeById(basicLink.getNodeTail());
                matrix[nodeIntegerMap.get(fromNode)][nodeIntegerMap.get(toNode)]=(long)weightOf(basicLink);
                matrix[nodeIntegerMap.get(toNode)][nodeIntegerMap.get(fromNode)]=(long)weightOf(basicLink);
            }
            ArrayList<Integer> route = routeCalculation(matrix, ori, dest);
            List<IBasicNetWork.BasicLink> returnLink = new ArrayList<>();
            if(route.size()!=0) {

                for (int i = 0; i < route.size() - 1; i++) {
                    IBasicNetWork.BasicNode from = commonNodes.get(route.get(i));
                    IBasicNetWork.BasicNode to = commonNodes.get(route.get(i + 1));
                    for (IBasicNetWork.BasicLink link : basicLinks) {
                        IBasicNetWork.BasicNode fromNode = project.searchNodeById(link.getNodeHead());
                        IBasicNetWork.BasicNode toNode = project.searchNodeById(link.getNodeTail());
                        if ((fromNode.equals(from) && toNode.equals(to) ||
                                (toNode.equals(from) && fromNode.equals(to)))) {
                            returnLink.add(link);
                            break;
                        }
                    }
                }
            }
            return returnLink;
        }


    @Override
    public List<IBasicNetWork.BasicLink> findOneMust(Project project,List<IBasicNetWork.BasicLink> links, List<IBasicNetWork.BasicNode> nodes, IBasicNetWork.BasicNode fromNode, IBasicNetWork.BasicNode toNode, IBasicNetWork.BasicNode mustNode) throws BaseException {
        if(fromNode==null||toNode==null||mustNode==null){
            return null;
        }
        //生成路由1和2
        List<IBasicNetWork.BasicLink> pathLink1 = findNoMust(project,links, nodes, fromNode, mustNode);
        if(pathLink1.size()==0)return null;
        List<IBasicNetWork.BasicLink> pathLink2 = findNoMust(project,links, nodes, mustNode, toNode);
        if(pathLink2.size()==0)return null;

        for (IBasicNetWork.BasicLink basicLink : pathLink2) {
            if(!pathLink1.contains(basicLink)){
                pathLink1.add(basicLink);
            }
        }
        return pathLink1;
    }


    @Override
    public List<IBasicNetWork.BasicLink> find(Project project,List<IBasicNetWork.BasicLink> links,List<IBasicNetWork.BasicNode> nodes,IBasicNetWork.BasicNode fromNode,IBasicNetWork.BasicNode toNode,String type,List<IBasicNetWork.BasicNode> mustNodes,List<Limit> limits) throws BaseException {
       if(links==null||nodes==null||fromNode==null||toNode==null||type==null||mustNodes==null||limits==null)return null;
       if(!nodes.contains(fromNode))throw new BaseException("首节点不存在");
       if(!nodes.contains(toNode))throw new BaseException("末节点不存在");
       if(!nodes.containsAll(mustNodes))throw new BaseException("必经节点不存在");
//使用深度优先算路，选取跨系统最少的路
        List<TraverseAlgorithm.Adjacency> adjacencyList = new ArrayList<>();//邻接数组
        Map<IBasicNetWork.BasicNode, Integer> nodeIntegerMap = new HashMap<>();//节点坐标字典
        Map<Integer, IBasicNetWork.BasicNode> integerCommonNodeMap = new HashMap<>();// 节点坐标反字典
        //创建字典、邻接数组
        Iterator<IBasicNetWork.BasicNode> commonNodeIterator = nodes.iterator();
        Integer index = 0;//坐标
        while (commonNodeIterator.hasNext()) {
            IBasicNetWork.BasicNode node = commonNodeIterator.next();
            // index->node;node->index;node[index]->adjacencyList[index]
            nodeIntegerMap.put(node, index);
            integerCommonNodeMap.put(index, node);
            TraverseAlgorithm.Adjacency adjacency = TraverseAlgorithm.createAdjacency();
            adjacencyList.add(adjacency);
            index++;
        }
        //根据策略构建邻接表
        for (IBasicNetWork.BasicLink link : links) {
            IBasicNetWork.BasicNode from = project.searchNodeById(link.getNodeHead());
            IBasicNetWork.BasicNode to = project.searchNodeById(link.getNodeTail());
            if (!nodes.contains(from) || !nodes.contains(to)) {
                continue;
            }
            int index0 = nodeIntegerMap.get(from);//找到起点的邻接数组坐标
            int index1 = nodeIntegerMap.get(to);// 找到终点的邻接数组坐标
            TraverseAlgorithm.Adjacency adjacency0 = TraverseAlgorithm.createAdjacency()
                    .andIndex(index1)
                    .andWeight(weightOf(link));
            adjacencyList.get(index0).andNextAdjacency(adjacency0);//创建邻接关系
            TraverseAlgorithm.Adjacency adjacency1 = TraverseAlgorithm.createAdjacency()
                    .andIndex(index0)
                    .andWeight(weightOf(link));
            adjacencyList.get(index1).andNextAdjacency(adjacency1);//创建邻接关系
        }
        int ori = nodeIntegerMap.get(fromNode);// 找到要算路的起点索引
        int des = nodeIntegerMap.get(toNode); //终点索引
        //深度优先算路 获得节点坐标组成的路由数组的数组
        List<List<Integer>> allPath = DFSAlgorithm.getInstance().search(adjacencyList, ori, des);
        // 找到含有必经节点的全部路由
        for (IBasicNetWork.BasicNode node : mustNodes) {
            List<List<Integer>> path = new ArrayList<>();
            for (List<Integer> route : allPath) {
                for (Integer i : route) {
                    IBasicNetWork.BasicNode commonNode = integerCommonNodeMap.get(i);
                    if (node.equals(commonNode)) {
                        path.add(route);
                        break;
                    }
                }
            }
            allPath = path;
        }
        //找跨系统最少的路
        int[] indexMap = new int[allPath.size()];
        Set<Integer> minSysIndexSet = new HashSet<>();
        //找到同系统数量
        for (int i = 0; i < allPath.size(); i++) {
            indexMap[i] = 0;// 索引为i的路由开始的跨系统数量为0
            // 遍历系统集合
            for (Limit limit : limits) {
                List<Integer> path = allPath.get(i);
                SystemLimit system = (SystemLimit) limit;
                for (int j = 0; j < path.size() - 1; j++) {
                    IBasicNetWork.BasicNode from = integerCommonNodeMap.get(path.get(j));
                    IBasicNetWork.BasicNode to = integerCommonNodeMap.get(path.get(j + 1));
                    if (system.inTheSomeSystem(from, to))
                        indexMap[i]++;//在同一个系统中同系统数量++
                }
            }
        }
        //找到同系统最多路由
        int max = 0;
        for (int i = 0; i < indexMap.length; i++) {
            max = indexMap[i] > max ? indexMap[i] : max;
        }
        for (int i = 0; i < indexMap.length; i++) {
            if (indexMap[i] == max) {
                minSysIndexSet.add(i);
            }
        }

        //在跨系统最少的情况下找权值最小的路
        Iterator iterator = minSysIndexSet.iterator();
        double minWeight = Double.MAX_VALUE;
        List<IBasicNetWork.BasicLink> res = new ArrayList<>();
        while (iterator.hasNext()) {
            List<Integer> path = allPath.get((Integer) iterator.next());
            List<IBasicNetWork.BasicLink> route = new ArrayList<>();// 路由
            Double weight = 0.0;
            for (int i = 0; i < path.size() - 1; i++) {
                IBasicNetWork.BasicNode from = integerCommonNodeMap.get(path.get(i));
               IBasicNetWork.BasicNode to = integerCommonNodeMap.get(path.get(i + 1));

                for (IBasicNetWork.BasicLink link : links) {
                    IBasicNetWork.BasicNode fromNode1 = project.searchNodeById(link.getNodeHead());
                    IBasicNetWork.BasicNode toNode1 = project.searchNodeById(link.getNodeTail());
                    if (fromNode1.equals(from) && toNode1.equals(to)) {
                        route.add(link);
                        weight += weightOf(link);
                    }
                    if (fromNode1.equals(to) && toNode1.equals(from)) {
                        weight += weightOf(link);
                        route.add(link);
                    }
                }
            }
            res = minWeight > weight ? route : res;
            minWeight = minWeight > weight ? weight : minWeight;
        }

      /*  //把里面的卫星和短波标识为不可再承载业务
        for (BasicLink link : res) {
            if (link instanceof Satellite || link instanceof ShortWave) {
                link.setValid(false);
            }
        }*/

        return res;
    }

    //根据链路选定的策略，计算链路的权值，有可能返回最大值，有溢出风险
    private double weightOf(IBasicNetWork.BasicLink link) {
        switch (strategy) {
            case StrategyString.HOP:
                return 1.0;
            case StrategyString.LENGTH:
                return link.getLength();
            default:
                double free = (double) link.getFreeRate() * 0.1;
                if (free <= 0) {
                    return Double.MAX_VALUE;//注意有溢出风险
                }
                double length = link.getLength();
                double weight = length / free;
                return weight;
        }
    }


    //计算承载链路
        private ArrayList<Integer> routeCalculation(long[][] matrix,int source,int dest){
            HashMap<Integer, String> path= new HashMap<>();
            long[] num =new long[matrix.length];
            boolean[] use=new boolean[matrix.length];
            use[source]=true;
            for (int i = 0; i < matrix.length; i++) {
                num[i]=matrix[source][i];
                path.put(i,source+","+i);
            }
            for (int i = 0; i < matrix.length; i++) {
                long min=Long.MAX_VALUE;
                int k=0;
                for (int j = 0; j < matrix.length; j++) {
                    if(!use[j]&&min>num[j]&&num[j]!=-1){
                        //找到每一次的最小值和最小值对应的索引
                        min=num[j];
                        k=j;
                    }
                }
                use[k]=true;
                for (int j = 0; j< matrix.length; j++) {
                    if(!use[j]){
                        if(matrix[k][j]!=-1&&((num[j]>(min+matrix[k][j]))||num[j]==-1)){
                            num[j]=min+matrix[k][j];
                            path.put(j,path.get(k)+","+j);
                        }
                    }
                }
            }
            ArrayList<Integer> route = new ArrayList<>();
            if(num[dest]>0) {
                String[] s = path.get(dest).split(",");
                for (String value : s) {
                    Integer r = Integer.valueOf(value);
                    route.add(r);
                }
            }
            return route;
        }

}

